package org.java.tree.rbtree;

import java.util.*;

class TestRB_Tree {
	static RB_Tree T = new RB_Tree();
	static int n = 0;
	static int h = 0;
	static int w = 0;
	static int go_h = 0;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		int[] A = { 10, 2, 12, 4, 6, 8, 1, 9, 7, 3, 11, 5 };
		for (int i = 0; i < A.length; i++) {
			T.RB_INSERT(T, T.createNode(A[i]));
			n++;
		}

		print_Tree();

		while (true) {
			System.out
					.print("\'I\' for insert, \'S\' for search, \'D\' for delete, \'Q\' for quit :");
			String choose = scanner.next();
			if (choose.equals("I")) {
				System.out.print("Input a number you want to insert: ");
				int insert = scanner.nextInt();
				T.RB_INSERT(T, T.createNode(insert));
				n++;
				System.out.println("Insert successfully!");
				print_Tree();
			} else if (choose.equals("S")) {
				System.out.print("Input the number you want to search: ");
				int search = scanner.nextInt();
				if (T.RB_SEARCH_RECURSION(T.root, search) != T.nil
						&& T.RB_SEARCH_ITERATIVE(T.root, search) != T.nil) {
					int key1 = T.RB_SEARCH_RECURSION(T.root, search).key;
					int key2 = T.RB_SEARCH_ITERATIVE(T.root, search).key;
					System.out.println("The result for recursion method is : "
							+ key1 + "\nThe result for iterative method is : "
							+ key2);
				} else {
					System.out
							.println("The Node you want to search isn\'t exist!");
				}
			} else if (choose.equals("D")) {
				System.out.print("Input the number you want to delete: ");
				int delete = scanner.nextInt();
				if (T.RB_SEARCH_RECURSION(T.root, delete) != T.nil) {
					T.RB_DELETE(T, T.RB_SEARCH_RECURSION(T.root, delete));
					n--;
					System.out
							.println("The Node has been deleted successfully!");
					print_Tree();
				} else {
					System.out
							.println("The Node you want to delete isn\'t exist!");
				}
			} else if (choose.equals("Q")) {
				System.exit(0);
			}
		}
	}

	public static void print_Tree() {
		go_h = 0;
		double bb = Math.log(n + 1);
		double aa = Math.log(2);
		h = (int) (2 * (bb / aa));
		w = (int) Math.pow(2, h);
		int k = ((int) Math.pow(2, h) - 1);

		RB_Tree.Node[] nodes = new RB_Tree.Node[k + 1];
		if (T.root != T.nil) {
			nodes[1] = T.root;
		}
		for (int i = 1; i <= k / 2; i++) {
			if (nodes[i] != T.nil && nodes[i] != null) {
				nodes[2 * i] = nodes[i].left;
				nodes[2 * i + 1] = nodes[i].right;
			}

		}
		for (int i = 1; i <= k; i++) {

			int a = 0x55 | 0x55 << 8;
			int b = 0x33 | 0x33 << 8;
			int c = 0x0f | 0x0f << 8;
			int mask1 = a | a << 16;
			int mask2 = b | b << 16;
			int mask3 = c | c << 16;
			int mask4 = 0xff | 0xff << 16;
			int mask5 = 0xff | 0xff << 8;
			int x1 = (i & mask1) + (i >> 1 & mask1);
			int x2 = (x1 & mask2) + (x1 >> 2 & mask2);
			int x3 = (x2 & mask3) + (x2 >> 4 & mask3);
			int x4 = (x3 & mask4) + (x3 >> 8 & mask4);
			int x5 = (x4 & mask5) + (x4 >> 16 & mask5);
			if (x5 == 1) {
				System.out.print("\n");
				go_h++;
			}
			int wn = (int) (Math.pow(2, go_h)) * 4;
			if (nodes[i] != T.nil && nodes[i] != null) {
				for (int j = 1; j < w / wn; j++) {
					System.out.print(" ");
				}
				System.out.print(nodes[i].key);
				if (nodes[i].color == false)
					System.out.print("R");
				else if (nodes[i].color == true)
					System.out.print("B");
				for (int j = 1; j < w / wn; j++) {
					System.out.print(" ");
				}
			} else {
				for (int j = 1; j < w / wn; j++) {
					System.out.print(" ");
				}
				System.out.print("  ");
				for (int j = 1; j < w / wn; j++) {
					System.out.print(" ");
				}
			}
		}
		System.out.print("\n");
	}

}
